package com.c2b.algorithm.newcoder.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">判断是不是二叉搜索树</a>
 * <p>给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。</p>
 * <p>二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。</p>
 * <p>数据范围：节点数量满足1≤n≤10^4，节点上的值满足−2^31 ≤val≤2^31−1 </p>
 *
 * @author c2b
 * @since 2023/3/14 14:57
 */
public class BM0034IsValidBST {

    public boolean isValidBST (TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currNode = queue.poll();
            if ((currNode.left != null && currNode.left.val >= currNode.val) || (currNode.right != null && currNode.right.val <= currNode.val)) {
                return false;
            }
            if (currNode.left != null) {
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                queue.offer(currNode.right);
            }
        }
        return true;
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3);
        treeNode.left = new TreeNode(2);
        treeNode.left.left = new TreeNode(1);
        treeNode.left.right = new TreeNode(4);
        treeNode.right = new TreeNode(5);
        BM0034IsValidBST bm0034IsValidBST = new BM0034IsValidBST();
        System.out.println(bm0034IsValidBST.isValidBST(treeNode));
    }
}
